package com.mdnote.practice.dp;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/10/23 0023
 * @description
 */
public class LeetCode5 {

    public static void main(String[] args) {
        LeetCode5 leetCode5 = new LeetCode5();
        String abcdc = leetCode5.center("aaa");
        System.out.println(abcdc);
    }

    public String dp(String s) {

        boolean[][] dp = new boolean[s.length()][s.length()];

        String res = "";
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j <= i; j++) {
                if (s.charAt(i) == s.charAt(j) && (i - j < 2 || dp[i - 1][j + 1])) {
                    dp[i][j] = true;
                    res = res.length() < i - j + 1 ? s.substring(j, i + 1) : res;

                }
            }
        }

        return res;
    }


    public String center(String s) {

        int centerLeft = 0, centerRight = 0;
        String res = "";

        for (int i = 0; i < s.length() * 2 - 1; i++) {

            centerLeft = i / 2;
            centerRight = centerLeft + (i & 1);

            while (centerLeft >= 0 && centerRight < s.length() && s.charAt(centerLeft) == s.charAt(centerRight)) {
                res = res.length() < centerRight - centerLeft + 1 ? s.substring(centerLeft, centerRight + 1) : res;
                centerLeft--;
                centerRight++;
            }
        }

        return res;
    }
}
